package cn.zzf.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <pre>{@code
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * }</pre>
 * <img width='200' height='160' src='https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png'/>
 * <pre>{@code
 * 示例 1：
 * 输入：digits = '23'
 * 输出：['ad','ae','af','bd','be','bf','cd','ce','cf']
 * 示例 2：
 * 输入：digits = ""
 * 输出：[]
 * 示例 3：
 * 输入：digits = '2'
 * 输出：['a','b','c']
 * }</pre>
 *
 * @author zzf
 * @date 2025-06-13 16:31
 */
public class T0017_LetterCombinations {

    private final static Map<Character, List<String>> map = new HashMap<>();

    static {
        map.put('2', List.of("a", "b", "c"));
        map.put('3', List.of("d", "e", "f"));
        map.put('4', List.of("g", "h", "i"));
        map.put('5', List.of("j", "k", "l"));
        map.put('6', List.of("m", "n", "o"));
        map.put('7', List.of("p", "q", "r", "s"));
        map.put('8', List.of("t", "u", "v"));
        map.put('9', List.of("w", "x", "y", "z"));
    }

    /**
     * 使用非递归的方式实现，由于每次都要计算索引位的变化，效率较递归更低。
     *
     * @param digits
     * @return
     * @author zzf
     * @date 2025-06-14 11:57
     */
    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.isEmpty()) return result;
        char[] array = digits.toCharArray();

        if (digits.length() == 1) {
            result.addAll(map.get(array[0]));
            return result;
        }
        // 用于记录每个数字遍历时的索引
        int[] idxs = new int[array.length];
        // 初始化
        for (int i = 0; i < array.length; i++) {
            idxs[i] = 0;
        }
        boolean stop = false;
        StringBuilder sb = new StringBuilder();
        do {
            for (int i = 0; i < array.length; i++) {
                List<String> charList = map.get(array[i]);
                int idx = idxs[i];
                sb.append(charList.get(idx));
            }
            result.add(sb.toString());
            sb.setLength(0);
            // 递增索引位（有点像进制，后面一位是否达到最大值，如果是，则进位，从低到高依次遍历，知道最高位超过最大值时停止）
            for (int i = array.length - 1; i >= 0; i--) {
                if (idxs[i] == map.get(array[i]).size() - 1) {
                    if (i == 0) {
                        stop = true;
                        break;
                    }
                    idxs[i] = 0;
                } else {
                    idxs[i]++;
                    break;
                }
            }
        } while (!stop);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(letterCombinations("234"));
        System.out.println(letterCombinations("23"));
        System.out.println(letterCombinations(""));
        System.out.println(letterCombinations("2"));
    }

}
